#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/19 14:40
# @USER    : Shengji He
# @File    : MaximumSubarray.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        Given an integer array nums, find the contiguous subarray (containing at least one number) which has the
        largest sum and return its sum.

        Example:
            Input: [-2,1,-3,4,-1,2,1,-5,4],

            Output: 6

            Explanation: [4,-1,2,1] has the largest sum = 6.
        Follow up:
        - If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach,
        which is more subtle.

        :param nums:
        :return:
        """
        pre, maxAns = 0, nums[0]
        for x in nums:
            pre = max(pre + x, x)
            maxAns = max(maxAns, pre)
        return maxAns


if __name__ == '__main__':
    S = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(S.maxSubArray(nums))
    print('done')
